package com.xiaoyu.backtracking;

import com.sun.jmx.remote.internal.ArrayQueue;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @program: DS_and_A
 * @description: 组合
 * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 示例:
 * 输入:n = 4, k = 2
 * 输出:
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 *
 * @author: YuWenYi
 * @create: 2021-06-03 10:09
 **/
public class Combination_77 {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();

        dfs(n, k, 1, res, path);

        return res;
    }

    public void dfs(int n,int k,int begin,List<List<Integer>> res,Deque<Integer> path){
        if (path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }
        //搜索起点的上界(i的最大值) + 接下来要选择的元素个数(即k-path.size()) - 1 = n,
        //例如n=6,k=3,假设已经选了1个元素了,那么还需要两个元素,按照公司,i=n-2+1=5,即i最大是5
        //假设此时i等于6,那么由于只剩一个元素6了,再怎么取也取不到2个数,所以这是可以被剪枝的!
        //由上面剪枝规则,可以得到:搜索起点的上界 = n - (k - path.size()) + 1,
        //因此i <= n - (k - path.size()) + 1
        //因此将i<=n  改为--> i <= n - (k - path.size()) + 1
        for (int i = begin; i <= n - (k - path.size()) + 1; i++) {
            path.push(i);

            dfs(n, k, i+1, res, path);

            path.pop();
        }
    }
    public static void main(String[] args) {
        Combination_77 combination_77 = new Combination_77();
        System.out.println(combination_77.combine(4, 2));
    }
}
